package com.jn.algorithm.day007.question23;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 江南大学1033190417
 * @date 2022/4/21 21:43
 */
public class Solution {

    //自己瞎写的，耗时超长
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode res = new ListNode(-1);
        ListNode pre = res;
        List<ListNode> list = new LinkedList<>(Arrays.asList(lists));
        while (list.size() != 0) {
            Iterator<ListNode> iterator = list.iterator();
            int min = Integer.MAX_VALUE;
            ListNode l = new ListNode(Integer.MIN_VALUE);
            while (iterator.hasNext()) {
                ListNode node = iterator.next();
                if (node == null) {
                    iterator.remove();
                    continue;
                }
                if (node.val < min) {
                    min = node.val;
                    l = node;
                }
            }
            if (l.val != Integer.MIN_VALUE) {
                pre.next = l;
                pre = pre.next;
                list.remove(l);
                l = l.next;
                if (l != null) {
                    list.add(l);
                }
            }
        }
        return res.next;
    }

    //分治法
    public ListNode mergeKLists2(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }

    //自己写


    public ListNode myMerge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return myMergeTwoLists(myMerge(lists, l, mid), myMerge(lists, mid + 1, r));
    }

    //合并两个链表,这个在21题写过了
    public ListNode myMergeTwoLists(ListNode a, ListNode b) {
        ListNode head = new ListNode(Integer.MIN_VALUE);
        ListNode pre = head;
        while (a != null && b != null) {
            if (a.val < b.val) {
                pre.next = a;
                a = a.next;
            } else {
                pre.next = b;
                b = b.next;
            }
            pre = pre.next;
        }
        if (a != null) {
            pre.next = a;
        }
        if (b != null) {
            pre.next = b;
        }
        return head.next;
    }


    public void print(ListNode node) {
        while (node != null) {
            System.out.print(node.val + "\t");
            node = node.next;
        }
    }

    public static void main(String[] args) {
        ListNode[] list = new ListNode[3];
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);
        list[0] = l1;
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(4);
        list[1] = l2;

        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);
        list[2] = l3;

        Solution solution = new Solution();
        solution.print(solution.myMergeTwoLists(l1, l2));

    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
